package main

import (
	"strconv"
	"strings"
)

/*
序列化二叉树

请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，
你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。

*/

/*
容易忽略的一个知识点。如果是满二叉树，那么遍历方式不影响最终结果。
1.先序遍历存储成[1,2,nul,nul,3,nul,] 类似这种的子序列。
2.先序遍历构造二叉树。依然要注意,Go的参数传递是值传递。递归从下一层跳出时，传递的值实际在上一层中没有改变，
类似回溯的效果。所以我们需要指针类型来改变[]string的长度。
*/

type TreeNode struct {
	Val   int
	Left  *TreeNode
	Right *TreeNode
}

func dfs(root *TreeNode, str *string) {
	if root == nil {
		*str += "null,"
		return
	}
	*str += strconv.Itoa(root.Val) + ","
	dfs(root.Left, str)
	dfs(root.Right, str)
	return
}
func Serialize(root *TreeNode) string {
	// write code her
	if root == nil {
		return ""
	}
	ans := ""
	dfs(root, &ans)
	return ans
}
func Deserialize(s string) *TreeNode {
	// write code here
	if len(s) == 0 {
		return nil
	}
	strs := strings.Split(s, ",")
	return deDfs(&strs)
}
func deDfs(str *[]string) *TreeNode {
	if (*str)[0] == "null" {
		*str = (*str)[1:] //没办法go是值传递，你需要改变切片的长度，让构造可以进行下去
		return nil
	}
	nums, _ := strconv.Atoi((*str)[0])
	*str = (*str)[1:]
	root := &TreeNode{Val: nums}
	if len(*str) != 0 {
		root.Left = deDfs(str)
	}
	if len(*str) != 0 {
		root.Right = deDfs(str)
	}
	return root
}

func main() {

}
